People throughout the world exchange enormous numbers of email messages. Due to the sheer volume of email messages sent and received by a typical person, it quickly becomes difficult for the person to identify email messages of interest. To help people identify email messages of interest, search functionality has been built into email client applications and email server applications. The search functionality finds email messages that contain text that conforms to queries entered by users of the email client applications. For example, the search functionality may find all email messages that contain the words “annual budget.”
To find email messages that contain text that conforms to queries, some email client applications generate search indexes and use the search indexes to identify email messages that contain the text. Search indexes can be implemented in many ways, including suffix trees, ordered trees, inverted indexes, citation indexes, ngram indexes, term document matrixes, and so on.